﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Twodi.Aspect.Interfaces;
using Microsoft.Xna.Framework;
using System.ComponentModel;
using System.Drawing;

namespace Twodi.Structs
{
    /// <summary>
    /// Representação de uma estrutura abstrata de dados organizados em uma QuadTree.
    /// </summary>
    /// <typeparam name="T">Tipo do Objeto, requer que possua posição.</typeparam>
    public class QuadTree<T> where T : IPositionAspect
    {
        /// <summary>
        /// Construtor padrão.
        /// </summary>
        /// <param name="parent">QuadTree pai deste.</param>
        /// <param name="capacity">Capacidade do QuadTree até gerar Split.</param>
        /// <param name="bounds">Região do QuadTree.</param>
        public QuadTree(QuadTree<T> parent, int capacity, Microsoft.Xna.Framework.Rectangle bounds)
            : this(capacity, bounds)
        {
            Parent = parent;
        }

        /// <summary>
        /// Construtor padrão.
        /// </summary>
        /// <param name="capacity">Capacidade do QuadTree até gerar Split.</param>
        /// <param name="bounds">Região do QuadTree.</param>
        public QuadTree(int capacity, Microsoft.Xna.Framework.Rectangle bounds)
            : this(capacity, new RectangleF(bounds.X, bounds.Y, bounds.Width, bounds.Height))
        {

        }

        /// <summary>
        /// Construtor padrão.
        /// </summary>
        /// <param name="parent">QuadTree pai deste.</param>
        /// <param name="capacity">Capacidade do QuadTree até gerar Split.</param>
        /// <param name="bounds">Região do QuadTree.</param>
        public QuadTree(QuadTree<T> parent, int capacity, RectangleF bounds)
            : this(capacity, bounds)
        {
            Parent = parent;
        }

        /// <summary>
        /// Construtor padrão.
        /// </summary>
        /// <param name="capacity">Capacidade do QuadTree até gerar Split.</param>
        /// <param name="bounds">Região do QuadTree.</param>
        public QuadTree(int capacity, RectangleF bounds)
        {
            Capacity = capacity;
            Bounds = bounds;
            Objects = new BindingList<T>();
            MinimumSize = new Vector2(100, 100);
        }

        /// <summary>
        /// Adicionar objeto.
        /// </summary>
        /// <param name="obj">Objeto a ser adicionado.</param>
        /// <returns>QuadTree no qual o objeto foi adicionado.</returns>
        public virtual QuadTree<T> Add(T obj)
        {
            QuadTree<T> result = null;

            if (Bounds.Contains(obj.PositionProperties.Position.X, obj.PositionProperties.Position.Y))
            {
                if (IsLeaf)
                {
                    if (Objects.Count < Capacity)
                    {
                        Objects.Add(obj);
                        return this;
                    }
                    else
                    {
                        Split();
                        if (!IsLeaf)
                        {
                            Arrange();
                            return AddLeaf(obj);
                        }
                        else
                        {
                            Capacity *= 2;
                            Objects.Add(obj);
                            return this;
                        }
                    }
                }
                else
                {
                    return AddLeaf(obj);
                }
            }

            return result;
        }

        /// <summary>
        /// Adicionar a um QuadTree filho.
        /// </summary>
        /// <param name="obj">Objeto a ser adicionado.</param>
        /// <returns>QuadTree no qual o objeto foi adicionado.</returns>
        private QuadTree<T> AddLeaf(T obj)
        {
            QuadTree<T> result = null;

            if ((result = TopLeft.Add(obj)) == null)
            {
                if ((result = TopRight.Add(obj)) == null)
                {
                    if ((result = BottomLeft.Add(obj)) == null)
                    {
                        if ((result = BottomRight.Add(obj)) == null)
                        {
                            throw new Exception("Erro ao adicionar o objeto.");
                        }
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Gerar filhos do QuadTree atual.
        /// </summary>
        private void Split()
        {
            float widht = Bounds.Width / 2;
            float height = Bounds.Height / 2;
            float xWidht = Bounds.X + widht;
            float yHeight = Bounds.Y + height;

            if (widht > this.MinimumSize.X && height > this.MinimumSize.Y)
            {
                TopLeft = new QuadTree<T>(this, Capacity, new RectangleF(Bounds.X, Bounds.Y, widht, height));
                TopRight = new QuadTree<T>(this, Capacity, new RectangleF(xWidht, Bounds.Y, widht, height));
                BottomLeft = new QuadTree<T>(this, Capacity, new RectangleF(Bounds.X, yHeight, widht, height));
                BottomRight = new QuadTree<T>(this, Capacity, new RectangleF(xWidht, yHeight, widht, height));
            }
        }

        /// <summary>
        /// Organizar objetos do QuadTree atual nos filhos.
        /// </summary>
        private void Arrange()
        {
            for (int i = 0; i < Objects.Count; i++)
            {
                AddLeaf(Objects[i]);
            }
            Objects.Clear();
        }

        /// <summary>
        /// Encontrar objeto no QuadTree e seus respectivos filhos, usando sua posição.
        /// </summary>
        /// <param name="obj">Posição do objeto a ser encontrado.</param>
        /// <returns>QuadTree que contem a posição do objeto.</returns>
        public virtual QuadTree<T> Find(Vector2 position)
        {
            if (Bounds.Contains(position.X, position.Y))
            {
                if (!IsLeaf)
                {
                    return FindLeaf(position);
                }
                else
                {
                    return this;
                }
            }

            return null;
        }

        /// <summary>
        /// Encontrar objeto no QuadTree, e seus respectivos filhos, usando sua posição e tamanho.
        /// </summary>
        /// <param name="position">Posição do componente.</param>
        /// <param name="size">Tamanho do componente.</param>
        /// <returns>QuadTrees que contem a posição e tamanho do objeto.</returns>
        public virtual List<QuadTree<T>> Find(Vector2 position, Vector2 size, bool origin = false)
        {
            List<QuadTree<T>> result = new List<QuadTree<T>>();

            QuadTree<T> quadTree = null;

            if (origin)
            {
                size *= 0.5f;

                if ((quadTree = Find(position - size)) != null)
                {
                    result.Add(quadTree);
                }

                if ((quadTree = Find(position + size)) != null)
                {
                    result.Add(quadTree);
                }

                if ((quadTree = Find(position + (size * new Vector2(-1, 1)))) != null)
                {
                    result.Add(quadTree);
                }

                if ((quadTree = Find(position + (size * new Vector2(1, -1)))) != null)
                {
                    result.Add(quadTree);
                }
            }
            else
            {
                if ((quadTree = Find(position)) != null)
                {
                    result.Add(quadTree);
                }

                if ((quadTree = Find(position + (size * Vector2.UnitX))) != null)
                {
                    result.Add(quadTree);
                }

                if ((quadTree = Find(position + (size * Vector2.UnitY))) != null)
                {
                    result.Add(quadTree);
                }

                if ((quadTree = Find(position + size)) != null)
                {
                    result.Add(quadTree);
                }
            }

            return result;
        }

        /// <summary>
        /// Encontrar objeto nos seus respectivos filhos, usando sua posição.
        /// </summary>
        /// <param name="obj">Posição do objeto a ser encontrado.</param>
        /// <returns>QuadTree que contem a posição do objeto.</returns>
        private QuadTree<T> FindLeaf(Vector2 position)
        {
            QuadTree<T> result = null;

            if ((result = TopLeft.Find(position)) == null)
            {
                if ((result = TopRight.Find(position)) == null)
                {
                    if ((result = BottomLeft.Find(position)) == null)
                    {
                        if ((result = BottomRight.Find(position)) == null)
                        {

                        }
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Remapear o objeto no QuadTree e seus respectivos filhos.
        /// Será executado um Find() para encontrar o antigo QuadTree que continha o objeto.
        /// </summary>
        /// <param name="obj">Objeto que foi movimentado.</param>
        /// <returns>Atual QuadTree que possui o objeto.</returns>
        public virtual QuadTree<T> Moved(T obj, Vector2 previous)
        {
            return Moved(obj, Find(previous));
        }

        /// <summary>
        /// Remapear o objeto no QuadTree e seus respectivos filhos.
        /// </summary>
        /// <param name="obj">Objeto que foi movimentado.</param>
        /// <param name="previous">Antigo QuadTree que continha o objeto.</param>
        /// <returns>Atual QuadTree que possui o objeto.</returns>
        public virtual QuadTree<T> Moved(T obj, QuadTree<T> previous)
        {
            QuadTree<T> result = null;

            if (Bounds.Contains(obj.PositionProperties.Position.X, obj.PositionProperties.Position.Y))
            {
                if (IsLeaf)
                {
                    if (this != previous)
                    {
                        if (previous != null)
                        {
                            previous.Objects.Remove(obj);
                        }
                        return Add(obj);
                    }
                    return this;
                }
                else
                {
                    return MovedLeaf(obj, previous);
                }
            }

            return result;
        }

        /// <summary>
        /// Remapear o objeto no filhos do QuadTree.
        /// </summary>
        /// <param name="obj">Objeto que foi movimentado.</param>
        /// <param name="previous">Antigo QuadTree que continha o objeto.</param>
        /// <returns>Atual QuadTree que possui o objeto.</returns>
        public virtual QuadTree<T> MovedLeaf(T obj, QuadTree<T> previous)
        {
            QuadTree<T> result = null;

            if ((result = TopLeft.Moved(obj, previous)) == null)
            {
                if ((result = TopRight.Moved(obj, previous)) == null)
                {
                    if ((result = BottomLeft.Moved(obj, previous)) == null)
                    {
                        if ((result = BottomRight.Moved(obj, previous)) == null)
                        {
                            throw new Exception("Erro ao mover o objeto.");
                        }
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Remover objeto do QuadTree e de seus respectivos filhos.
        /// </summary>
        /// <param name="obj">Objeto a ser removido.</param>
        /// <returns>QuadTree do qual o objeto foi removido.</returns>
        public virtual QuadTree<T> Remove(T obj)
        {
            if (!IsLeaf)
            {
                return RemoveLeaf(obj);
            }
            else if (Objects.Contains(obj))
            {
                Objects.Remove(obj);
                return this;
            }

            return null;
        }

        /// <summary>
        /// Remover objeto de seus respectivos filhos.
        /// </summary>
        /// <param name="obj">Objeto a ser removido.</param>
        /// <returns>QuadTree do qual o objeto foi removido.</returns>
        private QuadTree<T> RemoveLeaf(T obj)
        {
            QuadTree<T> result = null;

            if ((result = TopLeft.Remove(obj)) == null)
            {
                if ((result = TopRight.Remove(obj)) == null)
                {
                    if ((result = BottomLeft.Remove(obj)) == null)
                    {
                        if ((result = BottomRight.Remove(obj)) == null)
                        {
                            throw new Exception("Erro ao remover o objeto.");
                        }
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Tamanho minimo de um QuadTree.
        /// </summary>
        public Vector2 MinimumSize
        {
            get;
            protected set;
        }

        /// <summary>
        /// Quantidade de folhas.
        /// </summary>
        public int LeafCount
        {
            get
            {
                return IsLeaf ? 4 : (TopLeft.LeafCount + TopRight.LeafCount + BottomLeft.LeafCount + BottomRight.LeafCount);
            }
        }

        /// <summary>
        /// QuaTree é uma folha.
        /// </summary>
        public bool IsLeaf
        {
            get
            {
                return TopLeft == null;
            }
        }

        /// <summary>
        /// Capacidade do QuadTree.
        /// </summary>
        public int Capacity
        {
            get;
            protected set;
        }

        /// <summary>
        /// Região do QuadTree.
        /// </summary>
        public RectangleF Bounds
        {
            get;
            protected set;
        }

        /// <summary>
        /// Pai do QuadTree.
        /// </summary>
        public QuadTree<T> Parent
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho superior esquerdo do QuadTree.
        /// </summary>
        public QuadTree<T> TopLeft
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho superior direito do QuadTree.
        /// </summary>
        public QuadTree<T> TopRight
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho inferior esquerdo do QuadTree.
        /// </summary>
        public QuadTree<T> BottomLeft
        {
            get;
            protected set;
        }

        /// <summary>
        /// Filho inferior direito do QuadTree.
        /// </summary>
        public QuadTree<T> BottomRight
        {
            get;
            protected set;
        }

        /// <summary>
        /// Objetos contidos neste QuadTree.
        /// </summary>
        public BindingList<T> Objects
        {
            get;
            protected set;
        }

    }
}
